//
//  94. 二叉树的中序遍历.swift
//  手撕code
//
//  Created by xiaoZuDeMeng on 2024/3/6.
//

import Foundation

//https://leetcode.cn/problems/binary-tree-inorder-traversal/description/
//给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
//
//
//
//示例 1：
//
//
//输入：root = [1,null,2,3]
//输出：[1,3,2]
//示例 2：
//
//输入：root = []
//输出：[]
//示例 3：
//
//输入：root = [1]
//输出：[1]
//
//
//提示：
//
//树中节点数目在范围 [0, 100] 内
//-100 <= Node.val <= 100
//
//
//进阶: 递归算法很简单，你可以通过迭代算法完成吗？

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

func 二叉树的中序遍历(_ root: TreeNode?) -> [Int] {
    guard let root = root else {
        return []
    }
    var seq: [Int] = []
    seq += 二叉树的中序遍历(root.left)
    seq.append(root.val)
    seq += 二叉树的中序遍历(root.right)
    return seq
}
